#include <queue>
#include <vector>
using namespace std;

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    explicit ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution
{
    struct cmp
    {
        bool operator()(ListNode* a, ListNode* b)
        {
            return a->val > b->val;
        }
    };
public:
    static ListNode* mergeKLists(vector<ListNode*>& lists)
    {
        priority_queue<ListNode*, vector<ListNode*>, cmp> heap;

        for(auto e : lists)
        {
            if(e)
                heap.push(e);
        }

        ListNode* newhead = new ListNode(0);
        ListNode* prev = newhead;
        while(!heap.empty())
        {
            ListNode* tmp = heap.top();
            prev->next = tmp;
            heap.pop();
            prev = prev->next;
            if(tmp->next)   heap.push(tmp->next);
        }
        prev = newhead->next;
        delete newhead;
        return prev;
    }
};